modeltheoryfandomcom-20200213-history
Ehrenfeucht-Mostowski Model
The Ehrenfeucht-Mostowski construction is a construction which produces models in which few types are realized. 'Theorem. ' Let T be a complete theory with infinite models. Then for any \kappa \ge |T| , there is a model M \models T of cardinality \kappa such that if A \subset M , then at most |A| + |T| types over A are realized. Proof. First suppose that T has definable Skolem functions. Let \{a_\lambda\}_{\lambda < \kappa} be a non-constant indiscernible sequence of length \kappa in some model M_0 . We can find such an indiscernible sequence by extracting an indiscernible sequence from a non-constant sequence in an infinite model. Let M be \operatorname{dcl}(\{a_\lambda : \lambda < \kappa\}) . Because T has definable Skolem functions, M \preceq M_0 , so M \models T and \{a_\lambda\}_{\lambda < \kappa} is still indiscernible within M . The set \{a_\lambda\} is called the spine. Let A be a subset of M . Each element of A is in the definable closure of some finite subset of the spine, so we can find some A' contained in the spine, with A \subset \operatorname{dcl}(A') , and |A'| \le |A| + |T| . An element’s type over A is determined by its type over A' , because A \subset \operatorname{dcl}(A') . So it suffices to show that at most |A'| + |T| = |A| + |T| types over A' are realized. First we check that at most |A'| types are realized by tuples from the spine. We can write A' as \{a_\lambda : \lambda \in S\} for some S \subset \kappa with |S| = |A'| . The indiscernibility of the spine implies that \operatorname{tp}(a_{\lambda_1}a_{\lambda_2}\cdots a_{\lambda_n}/A') is entirely determined by how the \lambda_i relate to each other and how they relate to elements of S . That is, \operatorname{tp}(a_{\lambda_1} \cdots a_{\lambda_n}/A') is entirely determined by the following pieces of data: * Whether \lambda_i \le \lambda_j for each i, j . * The set \{x \in S : x \le \lambda_i\} for each i . * The set \{x \in S : x < \lambda_i\} for each i . Because S is well-ordered, there are only about |S| + \aleph_0 choices for the second and third bullet points. All told, there are therefore only |S| + \aleph_0 \le |A'| + |T| possibilities for \operatorname{tp}(a_{\lambda_1}\cdots a_{\lambda_n}/A') . Now if f(x_1,\ldots,x_n) is a 0-definable function, then \operatorname{tp}(f(a_{\lambda_1},\ldots,a_{\lambda_n})/A') depends only on \operatorname{tp}(a_{\lambda_1},\ldots,a_{\lambda_n}/A') , so there are at most |A'| + |T| types over A' realized by elements of the form f(a_{\lambda_1},\ldots,a_{\lambda_n}) . But all of M is in the definable closure of the spine, so every element of M is of this form. Since there are only |T| -many 0-definable functions, the total number of types over A' realized in M is at most (|A'| + |T|) \times |T| = |A'| + |T|. So at most |A'| + |T| types over A' are realized, completing the proof (in the case where we had definable Skolem functions). Now suppose T is arbitary. We can find a theory T' expanding T , which does have Skolem functions. This can easily be done in such a way that |T'| = |T| . By the above argument one gets a model M' of T' of size \kappa with the property that for every subset A of M' , at most |A| + |T| types over A are realized in M' . Let M be the reduct of M' to the original language. Then M \models T . If A \subset M , and a and b have the same T' -type over A , then they certainly have the same T -type over A within M , because T has fewer definable sets and relations to work with than T' . So there are at most as many T -types over A as there are T' -types over A , which is at most |A| + |T| . QED An important consequence of this result is the following, which is the first step of the proof of Morley’s Theorem. 'Corollary. ' Let T be a complete countable theory which is \kappa -categorical for some \kappa \ge \aleph_1 . Then T is \aleph_0 -stable (hence totally transcendental). Proof. Let \mathbb{U} be the monster model of T . Suppose T is not \aleph_0 -stable. Then we can find a countable set A over which there are uncountably many types. Realize \aleph_1 of these types and let B be the set of these realizations. Then |A \cup B| \le \aleph_1 \le \kappa , so by Löwenheim-Skolem we can find a model M of cardinality \kappa containing A \cup B . By the Ehrenfeucht-Mostowski construction, we can find a model M' of cardinality \kappa in which at most countably many types are realized over countable sets. By \kappa -categoricity, M \cong M' . So M also has the property that over countable sets, countably many types are realized. But over the countable set A \subset M , uncountably many types are realized in B \subset M , a contradiction. (It is a general fact that \aleph_0 -stable theories are totally transcendental. The proof goes as follows: if T failed to be totally transcendental, then RM(D) = \infty for some set D . Then one inductively builds a tree D, D_0, D_1, D_{00}, D_{01}, D_{10}, \ldots of non-empty \mathbb{U} -definable sets such that D_w is the disjoint union of D_{w0} and D_{w1} for every w \in \{0,1\}^{< \omega} , and such that each D_w has Morley rank \infty . This is the same construction used to prove that perfect sets in Polish spaces have cardinality 2^{\aleph_0} . At any rate, there are countably many D_w ’s, so the D_w ’s are all definable over some countable set A . Now each path through the tree yields a different type over A , so that there are uncountably many types over A , contradicting \omega -stability.) QED